Wednesday, December 14, 2005

Categorization of Geocodes (The Story of Locapoint: 6)

In previous posts, I introduced many Geocodes. Although there are many Geocodes, they can be categorized into three types. Every Geocode is belonging to one of them, or combination of them.

1. Mesh-Code Type
Subsequently divide target area into small area, and use mesh id number as a code. Mapcode of Denso is a good example.

2. Encoded type
Use the value of geographic parameters (latitude/longitude, or XYZ, etc) and encode them by specific algorism. Sony’s patent is a good example.

3. Database Type
Store a part or whole of location data into database, and use the key to identify its data as a code.
For example, Navigation-code(by Aishin A.W.) is replace degree part with city name. When decode, use city name to get degree data, and restore location data.

Each type havs following merit and demerit.

  Mesh-Code type Encoded type Database type
Short display digit Poor Good Good
readability Good Poor Good
maintainability Good Good Poor

I select “Encoded type” as a base of Locapoint. So my task is to improve readability.


Wednesday, December 07, 2005

Previously published "Geocodes" (The Story of Locapoint: 5)

Before designing a Locapoint, I had a research for previously published technologies, especially in Patent documents.

I guess everyone thought "Latitude and Longitude format is not convenient", like I did. So there are many 'Geocode's are proposed. There should be more and more code, but I will respectfully introduce some code that I found.
(notice: I wrote some comments on each Geocode. These comments and merit/demerit are my personal opinion and it is NOT an evaluation or blame for these Geocode.)

Mapcode (by Denso)
The Geocode developed by Denso Co. Denso is a Toyota Moter's group company, so Mapcode is basically developed for Car Navigation system.
Divide all Japan regions by some square shapes, and give them a number. Each square will be divided into 900 squares (30 times 30). In this fashion, square will be subsequently divided into 900 squares. With 10 digit of number, Mapcode can represent any place in Japan with 30 X 30 meter precision. 12 digits Mapcode can express 3 X 3 meter area.
The most unique point of Mapcode is optimization of its numbering. High populated area has priority assign of a small number. For example, the number which is assigned to top level and second level square of Tokyo area is 000 and 000. Thus any place in Tokyo is expressed by 000000XXXX -> XXXX. In this way, total length of code can be compressed. On the other hand, minor region still needs 10 digits.
This is a same concept as "G-code" for VCR recording. G-code assigns short (small) number for major TV programs, and leave long number for minor programs.
I guess the Mapcode is the first Geocode that uses this concept.
The demerit of Map code is covered area which is limited in Japan domestic use. In Mapcode's Web sight, Mapcode is preparing to export to other countries. However, to keep 30 X 30 meter precision by 10 digit of number, the square of cover area should be limited. Even if Mapcode is applied in various countries, the codes are not compatible among them.

Sony's patent
Sony has a patent of Geocode in USA.(US Patent 6,005,504)。
Convert Latitude and Longitude into steps (by unit of 0.1 second). Then Convert them into Binary, and join them. Finally, express this binary number in 37th Radix notation, and get 9 digits of code. To express notation with the base of 37, use number (0 to 9), Alphabet (A to Z), and "=".
The key of patent is to add error correcting code on it. For example, make it 10 digit, and use last digit as a check digit. This is a merit to detect input error, especially for this kind of 'Random-look' Code.

The Natural Area Coding System (by NAC Geographic Products Inc)
The Geocode developed by Dr.Xinhang Shen of Canadian venture company, NAC Geographic Products Inc.
According to its web site, it was developed around 1995. I think NAV is the most sophisticated in various Geocodes that I found.
Divide full range of Latitude and Longitude by 30, independently. Subsequently dividing by 30. Dislike other code, separate latitude and longitude data, instead of dividing "area". Expression of code is also display latitude data and longitude data separately. They are expressed in notation with base of 30, using number (0-9) and 20 alphabets. The letters that are not used are bawl (A, E, I, O, U) and (Y). NAC does not have any confusion between I and 1, or O and 0.
Dr. Shen proposes use NAC as a universal address.
For standard format, "5digit + blank + 5digit" have a precision of 0.0000148 degree (=1.6meter) in longitude direction at an equator, and 0.0000 74 degree (=0.8meter) in latitude direction. This has the highest precision in Geocode I saw.
NAC does not has digit limitation, so "6 digit blank 6 digit" can be X30 precision!
There are many merits. With using a "-", it can express areas. it can express "Height" data by format "XXXXX XXXXX HHHHH". Using a 30th radix notation, calculation affinity to degree (360 degree) is well.
I found NAC after I developed Locapoint. However, the concept of Locapoint is very close to NAC.

Compact text encoding (by Microsoft)
After denying the offer from NAC, Microsoft will apply US Patent of Geocode, which is very similar to NAC. Difference between NAC is, a)use small case (NAC:upper case), b)non-use continent is "l" (NAC:"Y"), c)there is no "blank" between latitude and longitude data, and d)the position of latitude and longitude data is opposite. Basically, the concept is exactly same as NAC.

New-Geocode (by Asia aerial survey)
Divide areas into square tile, express in binary, divide them by 6bit, and express it using Japanese "Hiragana" Characters (64 characters). Radix of 64 has good calculation affinity for computer usage.
Demerit is using Japanese Characters.

Navigation Code(by Aishin A.W.)
Express location by Degree, Minutes, and Second, then store ‘degree’s part in database, and use geographic name for its key.
For example, code is like this format :Tokyo23'56"12'33"

BINGEO(United States Patent 6,552,670)

A kind of "Mesh dividing" code. Each Mesh is square, and divided into 4 smaller squares. This smaller is assigned 00, 01, 10, and 11. Repeat this dividing until precision is OK.
For one level of mesh needs 2 byte. The merit of this code is affinity in computer usage, since this code is a binary.

There are more and more Geocode are proposed by individual, commercial companies, industry, or governments